package com.atguigui.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 1971.寻找图中是否存在路径
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/12/19 9:03
 */
public class P1971FindIfPathExistsInGraph {

    public static void main(String[] args) {
        Solution solution = new P1971FindIfPathExistsInGraph().new Solution();
        // TO TEST
    }

    class Solution {
        public boolean validPath(int n, int[][] edges, int source, int destination) {
            List<Integer>[] adj = new ArrayList[n];
            //初始化
            for (int i = 0; i < n; i++) {
                adj[i] = new ArrayList<Integer>();
            }
            //正反向添加
            for (int[] edge : edges) {
                int x = edge[0], y = edge[1];
                adj[x].add(y);
                adj[y].add(x);
            }
            //防止重复访问
            boolean[] visited = new boolean[n];
            return dfs(source, destination, adj, visited);
        }

        //深度优先
        private boolean dfs(int source, int destination, List<Integer>[] adj, boolean[] visited) {
            //开始节点和结束节点相同直接返回
            if (source == destination) {
                return true;
            }
            //防止重复访问
            visited[source] = true;
            for (int next : adj[source]) {
                //
                if (!visited[next] && dfs(next, destination, adj, visited)) {
                    return true;
                }
            }

            return false;
        }
    }
}
